#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=10100;
const int oo=100000000;

struct Edge {
	int x, y, v;
	void insert(int a, int b, int c){
		x=a; y=b; v=c;
	}
};

bool operator < (const Edge &a, const Edge &b){
	return a.v<b.v;
}

struct Node {
	int x, y, from;
};

bool operator < (const Node &a, const Node &b){
	return ( ( a.x > b.x ) || ( a.x == b.x ) && ( a.y > b.y ) );
}

/*struct LineTree {
	int min, wh;
};*/

Node p[maxn], pp[maxn], tmp;
Edge g[maxn << 2];
int n, m, t[maxn], wh[maxn], fa[maxn], tot;
int num[maxn], from[maxn];
//LineTree tree[maxn<<2];

int BinarySearch( int x ){
	int l, r, m;
	l=0; r=n-1;
	while (r>=l) {
		m=(l+r) >> 1;
		if ( t[m] < x )
			r = m - 1;
		else
			if ( t[m] > x )
				l = m + 1;
			else
				return m;
	}
}

/*void insert( int num, int x, int l, int r, int v, int w ){
	int m;
	if ( l==r ){
		if ( v<tree[ num ].min) {
			tree[ num ].min=v; tree[ num ].wh=w;
		}
		return;
	}
	m=( l + r ) >> 1;
	if ( x <= m )
		insert( num << 1, x, l, m, v, w);
	else
		insert( (num << 1) + 1, x, m+1, r, v, w );
	if ( v<tree[ num ].min) {
		tree[ num ].min=v; tree[ num ].wh=w;
	}	
}

void find( int num, int l, int r, int x, int y ){
	int m;
	if ( (l==x) && (r==y) ){
		if (tree[ num ].min < tmp.y) {
			tmp.x = tree[ num ].wh;
			tmp.y = tree[ num ].min;
		}
		return;
	}
	m=( l + r ) >> 1;
	if ( x > m )
		find( num << 1 + 1, m+1, r, x, y );
	else
		if ( y <= m )
			find( num << 1, l, m, x, y);
		else {
			find( num << 1, l, m, x, m);
			find( num << 1 + 1, m+1, r, m+1, y);
		}
}*/

void New_edge( int a, int b, int vv){
	g[ tot ].x=a; g[ tot ].y=b; g[ tot ].v=vv; tot++;
}

bool cmp( int a, int b ){
	return a>b;
}

void insert( int x, int v, int tt ){
	while ( x<=n ){
		if ( v<num[x] || num[x]==-1 ){
			num[x]=v; from[x]=tt;
		}
		x+=x&(-x);
	}
}

void find( int x ){
	while ( x>0 ){
		if ( num[x]!=-1 && num[x]<tmp.y ){
			tmp.x=from[x]; tmp.y=num[x];
		}
		x-=x&(-x);
	}
}

void add_edge(){
	int i, j;
	sort(p, p+n);
	for (i=0; i<n; i++)
		t[i]=p[i].y-p[i].x;
	sort(t, t+n, cmp);
	for (i=0; i<n; i++)
		wh[i]=BinarySearch( p[i].y-p[i].x );
	memset( num, -1, sizeof( num ) );
	insert( wh[0]+1, p[0].x+p[0].y, p[0].from );
	//insert( 1, wh[ 0 ], 0, n, p[i].x + p[i].y, 0);
	for (i=1; i<n; i++) {
		tmp.x=0; tmp.y=oo;
		find( wh[i]+1 );
		//find( 1, 0, n, wh[ i ], n );
		if ( tmp.y!=-1 )
			New_edge( p[i].from, tmp.x, tmp.y-p[i].x-p[i].y );
		insert( wh[i]+1, p[i].x+p[i].y, p[i].from );
		//insert( 1, wh[ i ], 0, n, p[i].x + p[i].y, i );
	}
}

int get_fa( int x ){
	int tmp, ff;

	ff=x;
	while ( fa[ ff ] >= 0 )
		ff = fa[ ff ];

	while ( fa[ x ] >=  0 ){
		tmp = fa[ x ];
		fa[ x ] = ff;
		x = tmp;
	}
	return ff;
}

void kruscal(){
	int i, now, fa1, fa2;

	now=0;
	sort( g, g+tot );
	memset( fa, -1, sizeof(fa) );
	for (i=0; i<tot; i++) {
		fa1 = get_fa( g[ i ].x );
		fa2 = get_fa( g[ i ].y );
		if (fa1!=fa2){
			now++;
			if (fa1<fa2) {
				fa[fa1]+=fa[fa2];
				fa[fa2]=fa1;
			} else {
				fa[fa2]+=fa[fa1];
				fa[fa1]=fa2;
			}
			if (now==n-m){
				printf("%d\n", g[i].v);
				return;
			}
		}
	}
}

int main(){

	int i;

	scanf("%d %d", &n, &m);
	for (i=0; i<n; i++){
		scanf("%d %d", &pp[i].x, &pp[i].y);
		pp[i].from=i;
	}

	//region 1
	for (i=0; i<n; i++) p[i]=pp[i];
	add_edge();

	//region 2
	for (i=0; i<n; i++){
		p[i].x=pp[i].y; p[i].y=pp[i].x; p[i].from=pp[i].from;
	}
	add_edge();

	//region 3
	for (i=0; i<n; i++){
		p[i].x=pp[i].x; p[i].y=-pp[i].y; p[i].from=pp[i].from;
	}
	add_edge();

	//region 4
	for (i=0; i<n; i++){
		p[i].x=-pp[i].y; p[i].y=pp[i].x; p[i].from=pp[i].from;
	}
	add_edge();

	kruscal();

}
